#include <vector>
#include <set>
#include <list>
#include <stdio.h>
#include <stdlib.h>


#include <stdlib.h>
#include <time.h>
using namespace std;

int N = 3;

class Graph
{
		
	
public:
	bool *Used;
	int size;
	bool **AdjacencyMatrix;
	vector< set<int> > PossibleLinks;
	set <int> Wining;
	Graph(int FieldSize, bool horizontal)
	{
		int n;
		n=FieldSize*(FieldSize+1);
		AdjacencyMatrix=new  bool*[n];
		for(int i=0;i<n;i++)
		{
			AdjacencyMatrix[i]=new bool[n];
		}
		Used=new bool[n];
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				AdjacencyMatrix[i][j]=false;
			}
			Used[i]=false;
		}
		size=n;
		//vector<list<int>> PossibleLinks;
		set<int> tmp;
		if(horizontal)
		{
			for(int i=0;i<FieldSize;i++)
			{
				for(int j=0;j<FieldSize+1;j++)
				{
					//cout<<i<<" "<<j<<":"<<endl; 
					if(i-1>=0)
					{
						tmp.insert((i-1)*(FieldSize+1)+j);
					//	cout<<(i-1)*(FieldSize+1)+j<<"\t";
					}
					if(j-1>=0)
					{
						tmp.insert((i*(FieldSize+1))+j-1);
					//	cout<<(i*(FieldSize+1))+j-1<<"\t";
					}
					if(j+1<=FieldSize)
					{
						tmp.insert((i*(FieldSize+1))+j+1);
					//	cout<<i*(FieldSize+1)+j+1<<"\t";
					}
					if(i+1<FieldSize)
					{
						tmp.insert((i+1)*(FieldSize+1)+j);
					//	cout<<(i+1)*(FieldSize+1)+j<<"\t";
					}
					//cout<<endl;
					//tmp.insert(size*size+size+2);
					PossibleLinks.push_back(tmp);
					tmp.clear();
				}
		
			}
		
			int *win=new int[FieldSize];
			for(int i=0;i<FieldSize;i++)
			{
				Wining.insert(i*(FieldSize+1)+FieldSize);
				//cout<<i*(FieldSize+1)+FieldSize;
			}
		}
		else
		{
			for(int i=0;i<FieldSize+1;i++)
			{
				for(int j=0;j<FieldSize;j++)
				{
					//cout<<i<<" "<<j<<":"<<endl; 
					if(i-1>=0)
					{
						tmp.insert((i-1)*(FieldSize)+j);
					//	cout<<(i-1)*(FieldSize)+j<<"\t";
					}
					if(j-1>=0)
					{
						tmp.insert((i*FieldSize)+j-1);
					//	cout<<(i*(FieldSize))+j-1<<"\t";
					}
					if(j+1<FieldSize)
					{
						tmp.insert((i*FieldSize)+j+1);
					//	cout<<i*(FieldSize)+j+1<<"\t";
					}
					if(i+1<=FieldSize)
					{
						tmp.insert((i+1)*(FieldSize)+j);
					//	cout<<(i+1)*(FieldSize)+j<<"\t";
					}
					//cout<<endl;
					//tmp.insert(size*size+size+2);
					PossibleLinks.push_back(tmp);
					tmp.clear();
					
				}
		
			}
		
			int *win=new int[FieldSize];
			for(int i=0;i<FieldSize;i++)
			{
				Wining.insert(FieldSize*FieldSize+i);
				//cout<<FieldSize*FieldSize+i;
			}
			Wining.insert(FieldSize*(FieldSize+2));
			
		}
	};

	bool RecSearch(int vertex)
	{
		Used[vertex]=true;
		for(int i=0; i<size;i++)
		{
			
			if(AdjacencyMatrix[vertex][i]&&(!(Used[i])))
			{
				//cout<<endl<<"step: "<<vertex<<"is connected to"<<i;
				Used[i]=true;
				if(Wining.find(i)!=Wining.end())
				{
					return true;
				}
				else
				{
					if(RecSearch(i))
						return true;
				}
			}
		}
		return false;
	}
	void AddEdge(int i,int j)
	{
		AdjacencyMatrix[i][j]=true;
		AdjacencyMatrix[j][i]=true;
		PossibleLinks[i].erase(j);
		PossibleLinks[j].erase(i);
		//cout<<"edge "<<i<<" to "<<j<<" added"<<endl;
	}
        void DelEdge(int i,int j)
	{
		AdjacencyMatrix[i][j]=false;
		AdjacencyMatrix[j][i]=false;
		PossibleLinks[i].insert(j);
		PossibleLinks[j].insert(i);
	}
        /*
	void ShowMatrix()
	{
		cout<<endl;
		for(int i=0;i<size;i++)
		{
			for(int j=0;j<size;j++)
			{
				cout<<AdjacencyMatrix[i][j]<<"  ";
			}
			cout<<endl;
		}
	}
        */

};
class GameField
{
	int size;
public:
        int lastv1,lastv2;
	Graph *G1,*G2;
	GameField(int n)
	{
		G1=new Graph(n,true);
		G2=new Graph(n,false);
		size=n;
	}
	bool Motion(int side, int v1, int v2)
	{
		if(side==1)
		{
			if(G1->AdjacencyMatrix[v1][v2])
			{
				//cout<<endl<<"link exists"<<endl;
				return false;
			}
			if((G1->PossibleLinks[v1].find(v2)!=(G1->PossibleLinks[v1].end()))||(G1->PossibleLinks[v2].find(v1)!=(G1->PossibleLinks[v2].end())))
			{
				lastv1=v1<v2?v1:v2;
				lastv2=v2<v1?v1:v2;
				//cout<<"successful motion"<<endl;
				G1->AddEdge(v1,v2);
				if(abs(v1-v2)==1)
				{
					set<int>::iterator it;
					int minim=v1<v2?v1:v2;
					int hor=minim/(size+1);
					int vert=minim%(size+1);
					//cout<<endl<<hor<<"  "<<vert;
					int limv1=hor*size+vert;
					int limv2=(hor+1)*size+vert;
					//cout << endl;
					//cout << endl<<"old lists"<<endl;
					//for (it=G2->PossibleLinks[limv1].begin(); it!=G2->PossibleLinks[limv1].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//for (it=G2->PossibleLinks[limv2].begin(); it!=G2->PossibleLinks[limv2].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//cout << endl;
					//cout<<endl<<"limits: "<<limv1<<" "<<limv2;
					//cout<<endl<<endl<<"new lists: "<<endl;
					G2->PossibleLinks[limv1].erase(limv2);
					G2->PossibleLinks[limv2].erase(limv1);
					//for (it=G2->PossibleLinks[limv1].begin(); it!=G2->PossibleLinks[limv1].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//for (it=G2->PossibleLinks[limv2].begin(); it!=G2->PossibleLinks[limv2].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
				}
				else
				{
					set<int>::iterator it;
					int maxim=v1>v2?v1:v2;
					int hor=maxim/(size+1);
					int vert=maxim%(size+1);
					int limv1=hor*size+vert;
					int limv2=limv1-1;
					//cout << endl;
					//cout << endl<<"old lists"<<endl;
					//for (it=G2->PossibleLinks[limv1].begin(); it!=G2->PossibleLinks[limv1].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//for (it=G2->PossibleLinks[limv2].begin(); it!=G2->PossibleLinks[limv2].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//cout << endl;
					//cout<<endl<<"limits: "<<limv1<<" "<<limv2;
					//cout<<endl<<endl<<"new lists: "<<endl;
					G2->PossibleLinks[limv1].erase(limv2);
					G2->PossibleLinks[limv2].erase(limv1);
					//for (it=G2->PossibleLinks[limv1].begin(); it!=G2->PossibleLinks[limv1].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//for (it=G2->PossibleLinks[limv2].begin(); it!=G2->PossibleLinks[limv2].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
				}
				return true;
			}
			else
			{
				//cout<<endl<<"correctness test failed!"<<endl;
				return false;
			}
		}
		if(side==2)
		{
			if(G2->AdjacencyMatrix[v1][v2])
			{
				//cout<<endl<<"link exists"<<endl;
				return false;
			}
			if(G2->PossibleLinks[v1].find(v2)!=(G2->PossibleLinks[v1].end())||G2->PossibleLinks[v2].find(v1)!=(G2->PossibleLinks[v2].end()))
			{
				lastv1=v1<v2?v1:v2;
				lastv2=v2<v1?v1:v2;
				//cout<<"successful motion"<<endl;
				G2->AddEdge(v1,v2);
				if(abs(v1-v2)==1)
				{
					set<int>::iterator it;
					int minim=v1<v2?v1:v2;
					int hor=minim/(size);
					int vert=minim%(size);
					//cout<<endl<<hor<<"  "<<vert;
					int limv1=vert*(size+1)+hor;
					int limv2=(vert+1)*(size+1)+hor;
					//cout << endl;
					//cout << endl<<"old lists"<<endl;
					//for (it=G1->PossibleLinks[limv1].begin(); it!=G1->PossibleLinks[limv1].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//for (it=G1->PossibleLinks[limv2].begin(); it!=G1->PossibleLinks[limv2].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//cout << endl;
					//cout<<endl<<"limits: "<<limv1<<" "<<limv2;
					//cout<<endl<<endl<<"new lists: "<<endl;
					G1->PossibleLinks[limv1].erase(limv2);
					G1->PossibleLinks[limv2].erase(limv1);
					//for (it=G1->PossibleLinks[limv1].begin(); it!=G1->PossibleLinks[limv1].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//for (it=G1->PossibleLinks[limv2].begin(); it!=G1->PossibleLinks[limv2].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
				}
				else
				{
					set<int>::iterator it;
					int minim=v1<v2?v1:v2;
					int hor=minim/(size);
					int vert=minim%(size);
					int limv1=hor*(size+1)+vert;
					int limv2=limv1+1;
					//cout << endl;
					//cout << endl<<"old lists"<<endl;
					//for (it=G1->PossibleLinks[limv1].begin(); it!=G1->PossibleLinks[limv1].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//for (it=G1->PossibleLinks[limv2].begin(); it!=G1->PossibleLinks[limv2].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//cout << endl;
					//cout<<endl<<"limits: "<<limv1<<" "<<limv2;
					//cout<<endl<<endl<<"new lists: "<<endl;
					G1->PossibleLinks[limv1].erase(limv2);
					G1->PossibleLinks[limv2].erase(limv1);
					//for (it=G1->PossibleLinks[limv1].begin(); it!=G1->PossibleLinks[limv1].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
					//for (it=G1->PossibleLinks[limv2].begin(); it!=G1->PossibleLinks[limv2].end(); ++it)
					//	 cout << " " << *it;
					//cout << endl;
				}
				return true;
			}
			else
			{
				//cout<<endl<<"correctness test failed!"<<endl;
				return false;
			}
		}
		return true;
	}
	void DefenceResponse()
	{
                bool winable=false;
                for(int i=0;i<size*(size+1);i++)
		{
			set<int>::iterator it;
			for(it=G1->PossibleLinks[i].begin();it!=G1->PossibleLinks[i].end();it++)
			{
				G2->AddEdge(i,*it);
				if(WinTest()==2)
				{
					G2->DelEdge(i,*it);
					if(Motion(2,i,*it))
					{
                                                winable=true;
                                                break;
						//cout<<"response obtained "<<i<<" "<<*it;
						//return ;
					}
				}
				G2->DelEdge(i,*it);
			}
		}
                if(!winable)
                {
		if(abs(lastv1-lastv2)==1)
		{
			int minim=lastv1<lastv2?lastv1:lastv2;
			int x=minim/(size+1);
			int y=minim%(size+1);
			if(y>0)
			{
				int x2=x;
				int y2=y-1;
				if(Motion(2,x2*size+y2,(x2+1)*size+y2))
				{
					//cout<<"response obtained "<<x2*size+y2<<" "<<(x2+1)*size+y2;
				}
				else
				{
					if(Motion(2,x2*size+y2+2,(x2+1)*size+y2+2))
					{
						//cout<<"response obtained "<<x2*size+y2+2<<" "<<(x2+1)*size+y2+2;
					}
					else
					{
						x2=x+1;
						y2=y-1;
						if(x2<size)
						{
							if(Motion(2,x2*size+y2,x2*size+y2+1))
							{
							        //cout<<"response obtained "<<lastv1<<" "<<lastv2;
							}
						}
						else
						{
							int k=rand()%size*(size+1);
							while(G2->PossibleLinks[k].empty())
							{
								k=rand()%size*(size+1);
							}
							if((G2->Wining.find(k)!=G2->Wining.end()&&(G2->Wining.find(*(G2->PossibleLinks[k].begin()))!=G2->Wining.end())))
							{
								if(Motion(2,k,*(G2->PossibleLinks[k].begin())))
								{
									//cout<<"response obtained "<<lastv1<<" "<<lastv2;
								}
							}
						}
					/*else
					{
						if(Motion(2,lastv1+1,lastv2+1))
						{
							cout<<"response obtained"<<lastv1+1<<" "<<lastv2+1;
						}
					}*/
					}
				}
			}
			if(y==0)
			{
				int x2=x;
				int y2=y+1;
				if(Motion(2,x2*size+y2,(x2+1)*size+y2))
				{
					//cout<<"response obtained "<<x2*size+y2<<" "<<(x2+1)*size+y2;
				}
				else
				{
					if(Motion(2,x2*size+y2+1,(x2+1)*size+y2+1))
					{
						////cout<<"response obtained "<<x2*size+y2+1<<" "<<(x2+1)*size+y2+1;
					}
					else
					{
						x2=x+1;
						y2=y;
						if(Motion(2,x2*size+y2,(x2)*size+y2+1))
						{
							////cout<<"response obtained "<<x2*size+y2<<" "<<(x2)*size+y2+1;
						}
						else
						{
							int k=rand()%size*(size+1);
							while(G2->PossibleLinks[k].empty())
							{
								k=rand()%size*(size+1);
							}
							if((G2->Wining.find(k)!=G2->Wining.end()&&(G2->Wining.find(*(G2->PossibleLinks[k].begin()))!=G2->Wining.end())))
							{
								if(Motion(2,k,*(G2->PossibleLinks[k].begin())))
								{
									////cout<<"response obtained "<<lastv1<<" "<<lastv2;
								}
							}
						}
					}
				}
			}
		}
		else
		{
			int minim=lastv1<lastv2?lastv1:lastv2;
			int x=minim/(size+1);
			int y=minim%(size+1);
			int x2=x;
			int y2=y-1;
			if(x2==size)
			{
				x2--;
			}
			if(y2>0)
			{
				if(Motion(2,x2*size+y2+1,(x2+1)*size+y2+1))
				{
						////cout<<"response obtained "<<x2*size+y2+1<<" "<<(x2+1)*size+y2+1;
				}
				else
				{
					if(Motion(2,x2*size+y2,(x2+1)*size+y2))
					{
							////cout<<"response obtained "<<x2*size+y2<<" "<<(x2+1)*size+y2;
					}
					else
					{
						x2=x+1;
						y2=y;
						if(Motion(2,x2*size+y2,(x2)*size+y2+1))
						{
								////cout<<"response obtained "<<x2*size+y2<<" "<<(x2)*size+y2+1;
						}
						else
						{
							int k=rand()%size*(size+1);
							while(G2->PossibleLinks[k].empty())
							{
								k=rand()%size*(size+1);
							}
							if(Motion(2,k,*(G2->PossibleLinks[k].begin())))
							{
								////cout<<"response obtained "<<lastv1<<" "<<lastv2;
							}
						}
					}
				}
			}
			else
			{
				y2=y;
				if(Motion(2,x2*size+y2,(x2+1)*size+y2))
				{
						////cout<<"response obtained "<<x2*size+y2<<" "<<(x2+1)*size+y2;
				}
				else
				{
						x2=x+1;
						y2=y;
						if(Motion(2,x2*size+y2,(x2)*size+y2+1))
						{
								////cout<<"response obtained "<<x2*size+y2<<" "<<(x2)*size+y2+1;
						}
						else
						{
							int k=rand()%size*(size+1);
							while(G2->PossibleLinks[k].empty())
							{
								k=rand()%size*(size+1);
							}
							if(Motion(2,k,*(G2->PossibleLinks[k].begin())))
							{
								////cout<<"response obtained "<<lastv1<<" "<<lastv2;
							}
						}
				}
			}
		}
                }
	};
	int WinTest()
	{
		for(int i=0;i<G1->size;i++)
		{
			G1->Used[i]=false;
			G2->Used[i]=false;
		}
		for(int i=0;i<size;i++)
		{
			if(G1->RecSearch(i*(size+1)))
			{
				////cout<<"i : "<<i*(size+1)<<endl<<endl;
				return 1;
			}
			if(G2->RecSearch(i))
			{
				return 2;
			}
		}
		return 0;
	}
	void StartRand()
	{
		int k=rand()%size*(size);
		////cout<<k<<" "<<k+size;
		Motion(2,k,k+size);

	}
	void ShowLimits()
	{
		////cout<<endl<<"limits for g1 :"<<endl;
		set<int>::iterator it;
		for(int i=0;i<G1->size;i++)
		{
			////cout<<endl<<i<<" :"<<endl;
			for(it=G1->PossibleLinks[i].begin();it!=G1->PossibleLinks[i].end();++it)
			{
				////cout<<*it<<" ";
			}
		}
	}
	void ShowLimits2()
	{
		////cout<<endl<<"limits for g2 :"<<endl;
		set<int>::iterator it;
		for(int i=0;i<G2->size;i++)
		{
			////cout<<endl<<i<<" :"<<endl;
			for(it=G2->PossibleLinks[i].begin();it!=G2->PossibleLinks[i].end();++it)
			{
				////cout<<*it<<" ";
			}
		}
	}
};
/*
void main()
{
	srand ( time(NULL) );
	////cout<<"field creation: "<<endl;
	GameField f(3);
	int a,b;	
	f.Motion(1,0,1);
	f.Motion(1,5,1);
	f.Motion(1,6,5);
	f.Motion(1,6,7);
	////cout<<f.WinTest();
	while(f.WinTest()==0)
	{
		////cout<<endl<<"enter 2 numbers: ";
		cin>>a;
		cin>>b;
		if(f.Motion(1,a,b))
		{
			if(f.WinTest()==1)
			{
				////cout<<"Congrats";
			}
			else
			{
				f.DefenceResponse();
				if(f.WinTest()==2)
				{
					////cout<<"bad luck";
				}
			}
		}
		////cout<<endl<<"state: "<<f.WinTest();
	}
	
	
	getch();

}
*/
